package com.lun.swordtowardoffer2.c04;

import com.lun.util.SinglyLinkedList.ListNode;

public class ReorderList {
	
	private static final ReverseList RL = new ReverseList();
	
	public void reorderList(ListNode head) {
		
		ListNode slow = head, prev = null;
		ListNode fast = slow.next;
		
		while(fast != null) {
			prev = slow;
			slow = slow.next;
			
			fast = fast.next;
			if(fast != null)
				fast = fast.next;
		}
		
		if(prev != null) {
			prev.next = null;
			mix(head, RL.reverseList(slow));
		}
	}

	private ListNode mix(ListNode head, ListNode reverse) {
		if(head == null) {
			return reverse;
		}else if(reverse == null){
			return head;
		}else{
			ListNode p1 = head.next, p2 = reverse.next;
			
			head.next = reverse;
			reverse.next = mix(p1, p2);
			return head;
		}
	}
}
